Sprite 1984

home *** CD-ROM | disk | FTP | other *** search

/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / lib / include / RCS / list.h,v < prev next >

Wrap

Text File | 1991-08-16 | 10.9 KB | 404 lines

head 1.5; branch ; access ; symbols sprited:1.5.1; locks ; strict; comment @ * @; 1.5 date 91.02.04.09.55.36; author ouster; state Exp; branches 1.5.1.1; next 1.4; 1.4 date 90.09.11.14.40.07; author kupfer; state Exp; branches ; next 1.3; 1.3 date 89.06.23.11.29.49; author rab; state Exp; branches ; next 1.2; 1.2 date 89.06.15.15.33.46; author shirriff; state Exp; branches ; next 1.1; 1.1 date 88.06.21.09.36.53; author ouster; state Exp; branches ; next ; 1.5.1.1 date 91.08.15.21.45.48; author kupfer; state Exp; branches ; next ; desc @@ 1.5 log @Added more parens in LIST_FORALL macro. @ text @/* * list.h -- * * Structures, macros, and routines exported by the List module. * * Copyright (C) 1985, 1988 Regents of the University of California * Permission to use, copy, modify, and distribute this * software and its documentation for any purpose and without * fee is hereby granted, provided that the above copyright * notice appear in all copies. The University of California * makes no representations about the suitability of this * software for any purpose. It is provided "as is" without * express or implied warranty. * * rcsid "$Header: /sprite/src/lib/include/RCS/list.h,v 1.4 90/09/11 14:40:07 kupfer Exp Locker: ouster $ SPRITE (Berkeley)" */ #ifndef _LIST #define _LIST #ifndef _SPRITE #include "sprite.h" #endif /* * This module defines the list abstraction, which enables one to link * together arbitrary data structures. Lists are doubly-linked and * circular. A list contains a header followed by its real members, if * any. (An empty list therefore consists of a single element, the * header, whose nextPtr and prevPtr fields point to itself). To refer * to a list as a whole, the user keeps a pointer to the header; that * header is initialized by a call to List_Init(), which creates an empty * list given a pointer to a List_Links structure (described below). * * The links are contained in a two-element structure called List_Links. * A list joins List_Links records (that is, each List_Links structure * points to other List_Links structures), but if the List_Links is the * first field within a larger structure, then the larger structures are * effectively linked together as follows: * * header * (List_Links) first elt. second elt. * ----------------- ----------------- ----------------- * ..-> | nextPtr | ----> | List_Links | ----> | List_Links |----.. * | - - - - - - - | | | | | * ..-- | prevPtr | <---- | | <---- | |<---.. * ----------------- - --- --- --- - - --- --- --- - * | rest of | | rest of | * | structure | | structure | * | | | | * | ... | | ... | * ----------------- ----------------- * * It is possible to link structures through List_Links fields that are * not at the beginning of the larger structure, but it is then necessary * to perform pointer arithmetic to find the beginning of the larger * structure, given a pointer to some point within it. * * A typical structure might be something like: * * typedef struct { * List_Links links; * char ch; * integer flags; * } EditChar; * * Before an element is inserted in a list for the first time, it must * be initialized by calling the macro List_InitElement(). */ /* * data structure for lists */ typedef struct List_Links { struct List_Links *prevPtr; struct List_Links *nextPtr; } List_Links; /* * procedures */ extern void List_Init _ARGS_((List_Links *headerPtr)); /* initialize a header to a list */ extern void List_Insert _ARGS_((List_Links *itemPtr, List_Links *destPtr)); /* insert an element into a list */ extern void List_ListInsert _ARGS_((List_Links *headerPtr, List_Links *destPtr)); /* insert a list into a list */ extern void List_Remove _ARGS_((List_Links *itemPtr)); /* remove an element from a list */ extern void List_Move _ARGS_((List_Links *itemPtr, List_Links *destPtr)); /* move an element elsewhere in a list */ /* * ---------------------------------------------------------------------------- * * List_InitElement -- * * Initialize a list element. Must be called before an element is first * inserted into a list. * * ---------------------------------------------------------------------------- */ #define List_InitElement(elementPtr) \ (elementPtr)->prevPtr = (List_Links *) NIL; \ (elementPtr)->nextPtr = (List_Links *) NIL; /* * Macros for stepping through or selecting parts of lists */ /* * ---------------------------------------------------------------------------- * * LIST_FORALL -- * * Macro to loop through a list and perform an operation on each member. * * Usage: LIST_FORALL(headerPtr, itemPtr) { * / * * * operation on itemPtr, which points to successive members * * of the list * * * * It may be appropriate to first assign * * foobarPtr = (Foobar *) itemPtr; * * to refer to the entire Foobar structure. * * / * } * * Note: itemPtr must be a List_Links pointer variable, and headerPtr * must evaluate to a pointer to a List_Links structure. * * ---------------------------------------------------------------------------- */ #define LIST_FORALL(headerPtr, itemPtr) \ for ((itemPtr) = List_First(headerPtr); \ !List_IsAtEnd((headerPtr),(itemPtr)); \ (itemPtr) = List_Next(itemPtr)) /* * ---------------------------------------------------------------------------- * * List_IsEmpty -- * * Macro: Boolean value, TRUE if the given list does not contain any * members. * * Usage: if (List_IsEmpty(headerPtr)) ... * * ---------------------------------------------------------------------------- */ #define List_IsEmpty(headerPtr) \ ((headerPtr) == (headerPtr)->nextPtr) /* * ---------------------------------------------------------------------------- * * List_IsAtEnd -- * * Macro: Boolean value, TRUE if itemPtr is after the end of headerPtr * (i.e., itemPtr is the header of the list). * * Usage: if (List_IsAtEnd(headerPtr, itemPtr)) ... * * ---------------------------------------------------------------------------- */ #define List_IsAtEnd(headerPtr, itemPtr) \ ((itemPtr) == (headerPtr)) /* * ---------------------------------------------------------------------------- * * List_First -- * * Macro to return the first member in a list, which is the header if * the list is empty. * * Usage: firstPtr = List_First(headerPtr); * * ---------------------------------------------------------------------------- */ #define List_First(headerPtr) ((headerPtr)->nextPtr) /* * ---------------------------------------------------------------------------- * * List_Last -- * * Macro to return the last member in a list, which is the header if * the list is empty. * * Usage: lastPtr = List_Last(headerPtr); * * ---------------------------------------------------------------------------- */ #define List_Last(headerPtr) ((headerPtr)->prevPtr) /* * ---------------------------------------------------------------------------- * * List_Prev -- * * Macro to return the member preceding the given member in its list. * If the given list member is the first element in the list, List_Prev * returns the list header. * * Usage: prevPtr = List_Prev(itemPtr); * * ---------------------------------------------------------------------------- */ #define List_Prev(itemPtr) ((itemPtr)->prevPtr) /* * ---------------------------------------------------------------------------- * * List_Next -- * * Macro to return the member following the given member in its list. * If the given list member is the last element in the list, List_Next * returns the list header. * * Usage: nextPtr = List_Next(itemPtr); * * ---------------------------------------------------------------------------- */ #define List_Next(itemPtr) ((itemPtr)->nextPtr) /* * ---------------------------------------------------------------------------- * The List_Insert procedure takes two arguments. The first argument * is a pointer to the structure to be inserted into a list, and * the second argument is a pointer to the list member after which * the new element is to be inserted. Macros are used to determine * which existing member will precede the new one. * * The List_Move procedure takes a destination argument with the same * semantics as List_Insert. * * The following macros define where to insert the new element * in the list: * * LIST_AFTER(itemPtr) -- insert after itemPtr * LIST_BEFORE(itemPtr) -- insert before itemPtr * LIST_ATFRONT(headerPtr) -- insert at front of list * LIST_ATREAR(headerPtr) -- insert at end of list * * For example, * * List_Insert(itemPtr, LIST_AFTER(otherPtr)); * * will insert itemPtr following otherPtr in the list containing otherPtr. * ---------------------------------------------------------------------------- */ #define LIST_AFTER(itemPtr) ((List_Links *) itemPtr) #define LIST_BEFORE(itemPtr) (((List_Links *) itemPtr)->prevPtr) #define LIST_ATFRONT(headerPtr) ((List_Links *) headerPtr) #define LIST_ATREAR(headerPtr) (((List_Links *) headerPtr)->prevPtr) #endif /* _LIST */ @ 1.5.1.1 log @Initial branch for Sprite server. @ text @d15 1 a15 1 * rcsid "$Header: /sprite/src/lib/include/RCS/list.h,v 1.5 91/02/04 09:55:36 ouster Exp $ SPRITE (Berkeley)" @ 1.4 log @Use function prototypes. @ text @d15 1 a15 1 * rcsid "$Header: /sprite/src/lib/include/RCS/list.h,v 1.3 89/06/23 11:29:49 rab Exp Locker: kupfer $ SPRITE (Berkeley)" d144 3 a146 3 for (itemPtr = List_First(headerPtr); \ !List_IsAtEnd((headerPtr),itemPtr); \ itemPtr = List_Next(itemPtr)) @ 1.3 log @*** empty log message *** @ text @d15 1 a15 1 * rcsid "$Header: /sprite/src/lib/include/RCS/list.h,v 1.2 89/06/15 15:33:46 shirriff Exp Locker: rab $ SPRITE (Berkeley)" d85 15 a99 5 void List_Init(); /* initialize a header to a list */ void List_Insert(); /* insert an element into a list */ void List_ListInsert(); /* insert a list into a list */ void List_Remove(); /* remove an element from a list */ void List_Move(); /* move an element elsewhere in a list */ @ 1.2 log @Added List_ListInsert declaration. @ text @d15 1 a15 1 * rcsid "$Header: /sprite/src/lib/include/RCS/list.h,v 1.1 88/06/21 09:36:53 ouster Exp Locker: shirriff $ SPRITE (Berkeley)" d23 1 a23 1 #endif _SPRITE d270 1 a270 1 #endif _LIST @ 1.1 log @Initial revision @ text @d15 1 a15 1 * rcsid "$Header: list.h,v 1.1 88/06/20 09:27:29 ouster Exp $ SPRITE (Berkeley)" d87 1 @